package xyz.scootaloo.oj.offer

import xyz.scootaloo.oj.ds.TreeNode

/**
 * @author flutterdash@qq.com
 * @since 2021/4/12 22:10
 */
class P55II {

    fun isBalanced(root: TreeNode?): Boolean {
        return recur(root) != -1
    }

    private fun recur(root: TreeNode?): Int {
        // 假如此节点为空, 则返回以 root 为根节点的树最大深度为0
        if (root == null)
            return 0
        val left = recur(root.left)
        if (left == -1)
            return -1
        val right = recur(root.right)
        if (right == -1)
            return -1
        return if (Math.abs(left - right) < 2)
            Math.max(left, right) + 1
        else
            -1
    }
}
